import java.util.Scanner;

public class demo {

//     淘宝网店
//    NowCoder在淘宝上开了一家网店。他发现在月份为素数的时候，当月每天能赚1元；否则每天能赚2元。
//      现在给你一段时间区间，请你帮他计算总收益有多少。
//    输入:
//2000 1 1 2000 1 31
//2000 2 1 2000 2 29
//    输出:
//62
//29


    // 是否是闰年
    public static boolean isLeapYear(int year) {
        return year%400==0 || (year%4==0 && year%100!=0);
    }

    // 当年全年的营业额
    public static int profitOfYear(int year) {
        //   1不是素数
        return 2*31+
                1*28+
                1*31+
                2*30+
                1*31+
                2*30+
                1*31+
                2*31+
                2*30+
                2*31+
                1*30+
                2*31+
                (isLeapYear(year)? 1 : 0);
    }

    // 每个月的营业额
    private static final int[] Days = {62,28,31,60,31,60,31,62,60,62,30,62};
    // 当年的营业额
    public static int profitOfThisYear(int year, int month, int day){
        int count = 0;
        for(int i=0; i<month-1; i++) {
            count += Days[i];
        }
        if (month==1 || month==4 || month==6 || month==8 || month==9 || month==10 || month==12) {
            count += 2*day;
        }else {
            count += day;
        }
        if(isLeapYear(year) && month>2) {
            count++;
        }
        return count;
    }

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int year, month, day, year2, month2, day2;
            int profit = 0;
            year = scanner.nextInt();
            month = scanner.nextInt();
            day = scanner.nextInt();
            year2 = scanner.nextInt();
            month2 = scanner.nextInt();
            day2 = scanner.nextInt();
            for(int i=year+1; i<year2; i++) {
                profit += profitOfYear(i);
            }
            // 判断是不是只有今年营业
            if (year != year2) {
                profit += profitOfYear(year) - profitOfThisYear(year,month,day-1);
                profit += profitOfThisYear(year2,month2,day2);
            }else {
                profit += profitOfThisYear(year2,month2,day2) - profitOfThisYear(year,month,day-1);
            }
            System.out.println(profit);
        }
    }




    // 斐波那契凤尾
//NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
//为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。
//    输入描述:
//输入有多组数据。
//每组数据一行，包含一个整数n (1≤n≤100000)。
//    输出描述:
//对应每一组输入，输出第n个斐波那契数的最后6位
    public static void main(String[] args) {
        long[] arr = new long[100000];
        arr[0] = 1;
        arr[1] = 2;
        int flag = -1;
        for (int i=2; i<100000; i++) {
            arr[i] = arr[i-1] + arr[i-2];
            if (flag==-1 && arr[i]>=1000000) {//注意这里是6个0
                flag = i + 1;
            }
            arr[i] = arr[i]%1000000;
        }

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            if (n<flag) {
                System.out.printf("%d\n", arr[n-1]);
            }else {
                System.out.printf("%06d\n", arr[n-1]);
            }
        }
    }
}
